﻿// 天使果冻（递推）
//https://ac.nowcoder.com/acm/problem/219641

//g[i] 前i个数中次大值 
//f[i] 前i个数中最大值 f[i]=max(f[i-1],arr[i])
//#include<iostream>
//using namespace std;
//
//const int N = 1e5 + 5;
//int arr[N], f[N], g[N];
//int q, n, x;
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> arr[i];
//
//    f[0] = arr[0];
//    g[0] = 0;
//
//    for (int i = 1; i < n; i++)
//    {
//        if (arr[i] >= f[i - 1])
//        {
//            g[i] = f[i - 1];
//            f[i] = arr[i];
//        }
//        else if (arr[i] > g[i - 1])
//        {
//            g[i] = arr[i];
//            f[i] = f[i - 1];
//        }
//        else
//        {
//            g[i] = g[i - 1];
//            f[i] = f[i - 1];
//        }
//    }
//    cin >> q;
//    while (q--)
//    {
//        cin >> x;
//        cout << g[x - 1] << endl;
//    }
//
//    return 0;
//}


//dd爱旋转（模拟）
//https://ac.nowcoder.com/acm/problem/221786	

//#include<iostream>
//using namespace std;
//
//const int N = 1005;
//int g[N][N];
//int n;
//
//void setRow()//行对称
//{
//    for (int i = 0; i < n / 2; i++)
//        for (int j = 0; j < n; j++)
//            swap(g[i][j], g[n - i - 1][j]);
//}
//
//void setCol()//列对称
//{
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n / 2; j++)
//            swap(g[i][j], g[i][n - j - 1]);
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//            cin >> g[i][j];
//    }
//
//    int row = 0, col = 0;
//    int q, x;
//    cin >> q;
//    while (q--)
//    {
//        cin >> x;
//        if (x == 1) row++, col++;
//        else row++;
//    }
//
//    row %= 2; col %= 2;
//    if (row) setRow();
//    if (col) setCol();
//
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//            cout << g[i][j] << ' ';
//        cout << endl;
//    }
//
//    return 0;
//}


//⼩红取数（动态规划-01背包+同余）
//https://www.nowcoder.com/practice/6a7b2b6c9e3a4f56b1db9f8ca08d889b?tpId=230&tqId=38958&ru=/exam/oj

//dp[i][j]前i个数中挑选，总和%k为j时的最大值;
//dp[i][j]=max(dp[i-1][j], dp[i-1][(j-a[i]%k+k)%k]+a[i]);
//初始化：dp[0][0]=0, else -0x3f

//#include <iostream>
//#include <cstring>
//using namespace std;
//
//typedef long long LL;
//const int N = 1005;
//LL n, k;
//LL a[N], dp[N][N];
//
//int main() {
//    cin >> n >> k;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//
//    memset(dp, -0x3f, sizeof(dp));
//    dp[0][0] = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 0; j < k; j++)
//        {
//            dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - a[i] % k + k) % k] + a[i]);
//        }
//    }
//    cout << (dp[n][0] <= 0 ? -1 : dp[n][0]);
//
//    return 0;
//}